International Patent Application No. PCT/AU2005/000580 published under WO 2005/103926 (to which U.S. patent application Ser. No. 11/111,946 and published under No. 2005-0262313 corresponds) in the name of the present applicant, discloses how different portions of an application program written to execute on only a single computer can be operated substantially simultaneously on a corresponding different one of a plurality of computers. That simultaneous operation has not been commercially used as of the priority date of the present application. International Patent Application Nos. PCT/AU2005/001641 (WO 2006/110,937) to which U.S. patent application Ser. No. 11/259,885 entitled: “Computer Architecture Method of Operation for Multi-Computer Distributed Processing and Co-ordinated Memory and Asset Handling” corresponds and PCT/AU2006/000532 (WO 2006/110,957) both in the name of the present applicant and both unpublished as at the priority date of the present application, also disclose further details. The contents of the specification of each of the abovementioned prior application(s) are hereby incorporated into the present specification by cross reference for all purposes.
Briefly stated, the abovementioned patent specifications disclose that at least one application program written to be operated on only a single computer can be simultaneously operated on a number of computers each with independent local memory. The memory locations required for the operation of that program are replicated in the independent local memory of each computer. On each occasion on which the application program writes new data to any replicated memory location, that new data is transmitted and stored at each corresponding memory location of each computer. Thus apart from the possibility of transmission delays, each computer has a local memory the contents of which are substantially identical to the local memory of each other computer and are updated to remain so. Since all application programs, in general, read data much more frequently than they cause new data to be written, the abovementioned arrangement enables very substantial advantages in computing speed to be achieved. In particular, the stratagem enables two or more commodity computers interconnected by a commodity communications network to be operated simultaneously running under the application program written to be executed on only a single computer.
Genesis of the Invention Non-commercial operation of a prototype multiple computer system indicates that not every machine or computer in the system utilises or needs to refer to (e.g. have a local copy of) every possible memory location. As a consequence, it is now realised that it is possible to operate a multiple computer system without the local memory of each machine being identical to every other machine, so long as the local memory of each machine is sufficient for the operation of that machine. That is to say, provided a particular machine does not need to refer to (for example have a local copy of) some specific memory locations, then it does not matter that those specific memory locations are not duplicated in that particular machine.
Briefly, it is known in the prior art that fragmentation is a phenomenon that leads to inefficiency in many forms of computer storage. Specifically, memory fragmentation is the phenomenon in which memory storage becomes divided into many small pieces over time. Memory fragmentation can occur for example when an application allocates and deallocates (“frees”) regions of memory of varying sizes, thereby leaving the allocated and deallocated regions interspersed. The result is that, fragmented memory can potentially become effectively unusable because it is broken up into many pieces that are not close together.
Non-commercial operation of a multiple computer system prototype operating as a replicated shared memory arrangement has unexpectedly revealed that an application program operating in such arrangement for an extended period of time (such as for example, hours or even days of continuous operation) is susceptible to fragmentation between the replicated application memory locations/contents/values and the non-replicated application memory locations/contents/values of the local allocated application memories of each member machine making up the replicated shared memory arrangement.
It has further been revealed through operation of the abovementioned prototype that replicated memory locations/contents/values often “live” far longer on average than unreplicated application memory locations/contents/values. For example, replicated application memory locations/contents/values typically take the form of shared data structures and/or shared contents and/or shared values between plural threads of the application program, such as for example queues, lists, shared caches, and the like. Typically, such shared data structures and/or shared contents and/or shared values persist beyond the average life-cycle (duration) of single threads. Un-replicated application memory locations/contents/values, however, are characterised as not being shared between plural threads (for example, thread-local storage, thread-local variables, and other thread-private data structures etc), and therefore such un-replicated application memory locations/contents/values typically do not persist beyond the average life-cycle (duration) of a single thread.
The consequences of the above described differing characteristics of replicated application memory locations/contents and non-replicated application memory locations/contents leads to wide-spread fragmentation of the allocated application memory between the replicated application memory location/contents and the non-replicated application memory locations/contents. The problem of “fragmentation” of allocated application memory manifests in numerous ways, such as for example delayed or slow memory initialisation/allocation time, reduced effective application memory capacity, and decreased efficiency in serialising and de-serialising the contents of transmission and receipt of replica memory update transmissions due to replicated memory locations being stored in a non-contiguous and fragmented manner.
Investigation has revealed that the above described fragmentation problems arise due to the manner in which local replica application memory locations/contents/values are allocated or stored to the allocated application memory of individual machines. When replicated application memory contents/values are stored to allocated application memory in an uncoordinated and/or un-organised manner, or when prior art allocation and/or storage arrangements of single independent machines are used, fragmentation of allocated application memory will typically result when operated in a replicated shared memory arrangement. As at the priority date, no specific allocation and/or storage arrangement of replicated application memory locations/contents/values for multiple computer system of a replicated shared memory arrangement is known that reduces or minimises the incidences of fragmentation between replicated application memory locations/contents/values and non-replicated application memory locations/contents/values for “long-running” replicated shared memory systems.